beyondbinaryfandomcom-20200215-history
Elliptic-Curve Cryptography
https://en.wikipedia.org/wiki/Elliptic-curve_cryptography "Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields." Intro https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Rationale "Public-key cryptography is based on the intractability of certain mathematical problems. Early public-key systems are secure assuming that it is difficult to factor a large integer composed of two or more large prime factors. For elliptic-curve-based protocols, it is assumed that finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point is infeasible: this is the "elliptic curve discrete logarithm problem" (ECDLP). The security of elliptic curve cryptography depends on the ability to compute a point multiplication and the inability to compute the multiplicand given the original and product points. The size of the elliptic curve determines the difficulty of the problem. The primary benefit promised by elliptic curve cryptography is a smaller key size, reducing storage and transmission requirements, i.e. that an elliptic curve group could provide the same level of security afforded by an RSA-based system with a large modulus and correspondingly larger key: for example, a 256-bit elliptic curve public key should provide comparable security to a 3072-bit RSA public key." Explanation http://blog.oleganza.com/post/162861219668/eli5-how-digital-signatures-actually-work "Elliptic curves allow special kind of arithmetic on points. Two points can be “added” to produce another, seemingly random, point on the elliptic curve: C = A + B" "Turns out, if you add point A a lot of times (in other words, multiply it by a large enough number) and get another point B, it will be hard to figure out what that number was, provided you are given only the original point A and the resulting point B. “Hard” means that to find out that number of additions, you cannot simply “divide” Bby A, but have to enumerate a lot of possible numbers x to check if x·A produces B. So if x is very large, larger than number of atoms in the universe, checking all possibilities will take too long to bother. At the same time, if one knows correct x, computing x·A is pretty fast." https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Theory "For current cryptographic purposes, an elliptic curve is a plane curve over a finite field (rather than the real numbers) which consists of the points satisfying the equation : y^2 = x^3 + ax + b, \, "along with a distinguished point at infinity, denoted ∞. (The coordinates here are to be chosen from a fixed finite field of characteristic not equal to 2 or 3, or the curve equation will be somewhat more complicated.)" Secret Key Exchange https://www.youtube.com/watch?v=NmM9HA2MQGI - Secret Key Exchange (Diffe-Helman) - Computerphile https://www.youtube.com/watch?v=NF1pwjL9-DE Elliptic Curves - Computerphile Security Quantum Computing https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Quantum_computing_attacks "Shor's algorithm can be used to break elliptic curve cryptography by computing discrete logarithms on a hypothetical quantum computer. The latest quantum resource estimates for breaking a curve with a 256-bit modulus (128-bit security level) are 2330 qubits and 126 billion Toffoli gates39. In comparison, using Shor's algorithm to break the RSA algorithm requires 4098 qubits and 5.2 trillion Toffoli gate gates for a 2048-bit RSA key, suggesting that ECC is an easier target for quantum computers than RSA. All of these figures vastly exceed any quantum computer that has ever been built, and estimates place the creation of such computers as a decade or more away." Category:Cryptography Category:Mathematics Category:Field Theory